package com.lenl.arithmetic.tenusablealgorithm.prim;

import java.awt.*;
import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-15 15:36
 * @description 普利姆算法解决修路问题
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        //测试图是否创建成功
        char[] data=new char[]{'A','B','C','D','E','F','G'};
        int verxs=data.length;
        //邻接矩阵的关系使用二维数组表示,10000表示两地不连通
        int[][] weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };
        //创建MGraph
        MGraph mGraph=new MGraph(verxs);
        //创建minTree
        MinTree minTree=new MinTree();
        minTree.createGraph(mGraph,verxs,data,weight);
        minTree.showGraph(mGraph);
        //测试普利姆算法
        minTree.prim(mGraph,1);

    }
}

//创建最小生成树
class MinTree{
    //创建图的邻接矩阵
    public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight){
        int i,j;
        for (i=0;i<verxs;i++){
            graph.data[i]=data[i];
            for (j=0;j<verxs;j++){
                graph.weight[i][j]=weight[i][j];
            }
        }
    }

    //显示图的邻接矩阵
    public void showGraph(MGraph graph){
        for(int[] link:graph.weight){
            System.out.println(Arrays.toString(link));
        }
    }
    //编写prim算法，得到最小生成树

    /**
     *
     * @param graph 图
     * @param v 从图的第几个顶点开始生成
     */
    public void prim(MGraph graph,int v){

        int[] visited=new int[graph.verxs];//标记顶点是否访问过，默认都为0
        //把当前节点标记为已访问
        visited[v]=1;
        //h1与h2记录两个顶点的下标
        int h1=-1;
        int h2=-2;
        int minWeight=10000;//初始化为最大，后面会被替换
        for (int k=1;k<graph.verxs;k++){
            //有graph.verxs个顶点，graph.verxs-1条边，所以从1开始

            //确定每一次生成的子图，和哪个节点的距离最近
            for (int i=0;i<graph.verxs;i++){ //i节点表示访问过的节点
                for (int j=0;j<graph.verxs;j++){ //j节点表示还没当问过的节点
                    if(visited[i]==1&&visited[j]==0&& graph.weight[i][j]<minWeight){
                        //替换minWeight，寻找已经访问过的节点和为访问节点间权值最小的边
                        minWeight=graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }

            //找到一条边最小
            System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值："+minWeight);
            //将节点标记为已经访问
            visited[h2]=1;
            //重置minWeigh
            minWeight=10000;

        }

    }


}


class MGraph{
    int verxs;//表示图的节点个数
    char[] data;//存放节点数据
    int[][] weight;//存放边，邻接矩阵

    public MGraph(int verxs){
        this.verxs=verxs;
        data=new char[verxs];
        weight=new int[verxs][verxs];
    }

}
